﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <sstream>
#include <cstring>
using namespace std;

//class Solution {
//public:
//    int findTargetSumWays(vector<int>& nums, int target) {
//        int n = nums.size();
//        int sum = 0;
//        for (auto e : nums) sum += e;
//        int a = (sum + target) / 2;
//        if ((target + sum) % 2 != 0 || a < 0) return 0;
//
//        vector<int> dp(a + 1);
//        dp[0] = 1;
//
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = a; j >= 0; j--)
//            {
//                if (j >= nums[i - 1]) dp[j] += dp[j - nums[i - 1]];
//            }
//        }
//        return dp[a];
//    }
//};


//class Solution {
//public:
//    int lastStoneWeightII(vector<int>& stones) {
//        int n = stones.size();
//        int sum = 0;
//        for (auto e : stones) sum += e;
//        int V = sum / 2;
//
//        vector<vector<int>> dp(n + 1, vector<int>(V + 1));
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 1; j <= V; j++)
//            {
//                dp[i][j] = dp[i - 1][j];
//                if (j >= stones[i - 1]) dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
//            }
//        }
//        return sum - 2 * dp[n][V];
//    }
//};